Vamos a seguir con nuestra serie sobre 'python, fuente de sabiduria' hablando sobre la multiplicación.
¿Te has preguntado alguna vez cómo se multiplican dos números en un ordenador o calculadora? Normalmente, los circuitos de los procesadores incluyen operaciones básicas como la multiplicación de enteros de tamaño pequeño. Sobre estas operaciones básicas se construye todo lo demás.
El caso que nos ocupa hoy, multiplicar números enteros muy grandes, se consigue mediante el uso de algoritmos vía software. Una forma sencilla de calcular enteros es usando la misma metodología que usábamos en la escuela, con la tabla de multiplicar del uno al diez y con sumas:
23958233
5830 ×
------------
00000000 ( = 23,958,233 × 0)
71874699 ( = 23,958,233 × 30)
191665864 ( = 23,958,233 × 800)
119791165 ( = 23,958,233 × 5,000)
------------
139676498390 ( = 139,676,498,390 )
(ejemplo extraído de wikipedia)
El algoritmo que hace uso de esa metodología se suele llamar long, grade-school, naïve,..., multiplication. En este caso vamos a hacer una implementación sucia de este algoritmo descomponiendo el 'multiplicador' en dígitos que multiplicaremos al 'multiplicando':
In [1]:
def naive(x, y):
total = 0
yy = [int(i) for i in str(y)]
for i, yyy in enumerate(yy[::-1]):
total += x * yyy * (10 ** i)
return total
Para el ejemplo anterior (multiplicando = 23958233 y multiplicador = 5830) lo que estariamos haciendo sería lo siguiente:
Esta es una forma de hacer multiplicaciones pero cuando los números involucrados en la multiplicación son muy grandes podemos encontrarnos con problemas de rendimiento y perder mucho tiempo haciendo un cálculo.
Como en el desarrollo de Python hay gente muy inteligente, si buceas por el código fuente de Python verás que para multiplicación de long's se usa el algoritmo de la multiplicación rápida de Karatsuba. ¿Y quién demonios es este japonés? Pues este japonés es un ruso al que, con 23 añitos (en 1960), se le ocurrió llevar la contraria al mismísimo Kolmogorov.
Lo mejor es que le echéis un ojo a la siguiente entrada (o en la Wikipedia en español) para entender más claramente el funcionamiento (DRY). Básicamente, de lo que se trata es de minimizar el número de multiplicaciones (aunque no siempre se consigue) usando una estrategia de 'divide y vencerás'.
A continuación os dejo una implementación muy compacta que he encontrado en project nayuki (si no entendéis algo del código preguntad en los comentarios):
In [2]:
## http://nayuki.eigenstate.org/res/karatsuba-multiplication/karatsuba.py
## http://nayuki.eigenstate.org/page/karatsuba-multiplication
_CUTOFF = 1024
def kara(x, y):
if x.bit_length() <= _CUTOFF or y.bit_length() <= _CUTOFF: # Base case
#print('naive')
return naive(x, y)
else:
#print('karatsuba')
n = max(x.bit_length(), y.bit_length())
half = (n + 32) // 64 * 32
mask = (1 << half) - 1
xlow = x & mask
ylow = y & mask
xhigh = x >> half
yhigh = y >> half
a = kara(xhigh, yhigh)
b = kara(xlow + xhigh, ylow + yhigh)
c = kara(xlow, ylow)
d = b - a - c
return (((a << half) + d) << half) + c
Bien, pues vamos a ver si esto es capar de optimizar mi función naive. Para ello vamos a multiplicar el siguiente número (tened cuidado si vuestro ordenador no es muy potente ya que el cálculo se puede llegar a alargar):
In [3]:
num = 1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890*(10**14000)
#print(num.bit_length())
print(num)
Usando la función naive.
In [4]:
a = naive(num, num)
%timeit naive(num, num)
Usando la función kara
In [5]:
b = kara(num, num)
%timeit kara(num, num)
In [6]:
print(a == b)
print(1.31 / 0.173)
Vemos que hemos conseguido una ganancia de 7.5x!!!
Aunque si comprobamos como lo hace Python vemos que no hemos hecho una gran optimización (aunque no era lo importante de esta entrada):
In [7]:
%timeit num * num
Parece que solo es alrededor de 375 veces más rápido ;-)
Este código lo he probado en Python 3.3, si veis alguna errata o alguna barbaridad que haya podido decir, por favor, avísadme.
Esta entrada la puedes descargar en formato notebook desde nuestro repositorio en github.
P.D.: Pretendía que esta entrada fuera más rigurosa y completa pero mi tiempo se ha visto disminuido de forma drástica últimamente. La familia manda :-)